#include <cstdio>
#include <vector>
#include <chrono>
#include <random>

int partition(std::vector<int>& nums, int low, int high)
{
    /*
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(low, high);
    std::swap(nums[low], nums[dis(gen)]);
    */
    int i = low, j = high, privot = nums[low];
    while (i < j)
    {
        while (i < j && nums[j] > privot)
            j--;
        while (i < j && nums[i] <= privot)
            i++;
        if (i < j)
            std::swap(nums[i++], nums[j--]);
    }
    if (nums[i] > privot) 
    {
        std::swap(nums[low], nums[i - 1]);
        return i - 1;
    }
    std::swap(nums[low], nums[i]);
    return i;
}

void quickSort(std::vector<int>& nums, int low, int high)
{
    if (low < high)
    {
        int mid = partition(nums, low, high);
        quickSort(nums, low, mid - 1);
        quickSort(nums, mid + 1, high);
    }
}

int main(int argc, char const *argv[])
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, 9999);
    std::vector<int> nums;
    for (int i = 0; i < 10000000; i++)
        nums.push_back(dis(gen));
    auto start = std::chrono::high_resolution_clock::now();
    quickSort(nums, 0, nums.size() - 1);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    printf("elapsed time: %f s\n", elapsed.count());
    for (int i = 1; i < nums.size(); i++)
    {
        if (nums[i] < nums[i - 1])
        {
            printf("error! %d < %d\n", nums[i], nums[i-1]);
            return 1;
        }
    }
    printf("success!\n");
    return 0;
}
